---
title: "L2-049 鱼与熊掌"
created: 2025-11-28
tags:
  - 算法
---

# L2-049 鱼与熊掌

## 题目 [L2-049 鱼与熊掌](https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?problemSetProblemId=1781658570803388424&page=1)

![[image-20f5c440.png]]

## 思路分析

## 代码实现

直接用set写只能13/25

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int,int>;
using Pll = pair<ll,ll>;
int dx[4]={-1,0,-1,0},dy[4]={0,1,0,-1};
const int inf = 0x3f3f3f3f;
/*
给定 n 个人对 m 种物品的拥有关系。
对其中任意一对物品种类（例如“鱼与熊掌”），
请你统计有多少人能够兼得？
*/

vector<set<int>> people;

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,m;cin>>n>>m;
	people.resize(n+1);
	for(int i=1;i<=n;i++){
		int k;cin>>k;
		int pz;
		while(k--){
			cin>>pz;
			people[i].insert(pz);
		}
	}

	int q;cin>>q;
	while(q--){
		int a,b;cin>>a>>b;
		int cnt=0;
		for(auto p:people){
			if(p.count(a) && p.count(b)){
				cnt++;
			}
		}
		cout<<cnt<<endl;
	}

	return 0;
}
```

换个角度（倒排索引） 从物品入手 存储每个物品的拥有者有哪些 然后对查询物品找交集

21/25

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int,int>;
using Pll = pair<ll,ll>;
int dx[4]= {-1,0,-1,0},dy[4]= {0,1,0,-1};
const int inf = 0x3f3f3f3f;
/*
给定 n 个人对 m 种物品的拥有关系。
对其中任意一对物品种类（例如“鱼与熊掌”），
请你统计有多少人能够兼得？
*/

unordered_map<int,unordered_set<int>> items;

int main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,m;
	cin>>n>>m;

	for(int i=1; i<=n; i++) {
		int k,item;
		cin>>k;

		while(k--) {
			cin>>item;
			items[item].insert(i);
		}
	}

	int q;
	cin>>q;
	while(q--) {
		int a,b;
		cin>>a>>b;

		const auto& seta = items[a];
		const auto& setb = items[b];
		if(seta.size()>setb.size()) {
			swap(a,b);
		}

		int cnt=0;
		for(auto p:items[a]) {
			if(items[b].count(p)) {
				cnt++;
			}
		}

		cout<<cnt<<endl;
	}

	return 0;
}
```

极端数据（比如一个物品有几万人拥有）导致哈希查找效率下降或者 cache miss

使用vector 排序后，两指针线性扫交集

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int,int>;
using Pll = pair<ll,ll>;
int dx[4]={-1,0,-1,0},dy[4]={0,1,0,-1};
const int inf = 0x3f3f3f3f;

unordered_map<int, vector<int>> items;

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; ++i) {
		int k, item;
		cin >> k;
		while (k--) {
			cin >> item;
			items[item].push_back(i);
		}
	}

	for (auto& people : items) {
		sort(people.second.begin(), people.second.end());
	}

	int q;
	cin >> q;
	while (q--) {
		int a, b;
		cin >> a >> b;
		const auto& pa = items[a];
		const auto& pb = items[b];
		int cnt = 0;
		int i = 0, j = 0;
		while (i < pa.size() && j < pb.size()) {
			if (pa[i] == pb[j]) {
				++cnt;
				++i;
				++j;
			} else if (pa[i] < pb[j]) {
				++i;
			} else {
				++j;
			}
		}
		cout << cnt << '\n';
	}

	return 0;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[L2-048 寻宝图|L2-048 寻宝图]] 🏠 [[00-天梯赛]] ➡️ [[L2-050 懂蛇语|L2-050 懂蛇语]]